/*
    动态规划：dp(n)表示以1...n这n个节点可组成的二叉搜索树的数量
    1...n
    如果i作为根节点：1...i-1这i-1个节点在左子树中。i+1...n这n-i个节点在右子树中。
    i-1个节点可组成的二叉搜索树的数量为dp(i-1)
    n-i个节点可组成的二叉搜索树的数量为dp(n-i)
    注意：不用关心节点取值，只需关心节点数量
    那么以i为根节点可组成的二叉搜索树的数量即为这两个的笛卡尔积：dp(i-1)*dp(n-i)

    依次将1至n作为根节点，则可推出dp(n) = 依次将1至n的dp(i-1)*dp(n-i)之和
*/
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1; // 表示当序列长度为0（空树），只有一种情况。注意不能为0
        dp[1] = 1; // 表示当序列长度为1（只有根节点），也只有一种情况

        // 依次计算i个节点可组成的二叉搜索树的数量
        // i为n时，就是我们想要的结果
        for (int i = 2; i <= n; i++) {
            // 依次将1到i的每个数字作为根节点
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
};

int main() {
    cout << Solution().numTrees(3) << endl;
    return 0;
}